package leetcode.editor.offer;

// 54. 二叉查找树的第 K 个结点
// https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/submissions/
class ErChaSouSuoShuDeDiKdaJieDianLcof {
    public static void main(String[] args) {
        Solution solution = new ErChaSouSuoShuDeDiKdaJieDianLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    class Solution {
        /*public int kthLargest(TreeNode root, int k) {
            traversal(root, k);
            return k > list.size() ? 0 : list.get(list.size() - k);
        }

        List<Integer> list = new ArrayList<>();

        public void traversal(TreeNode root, int k) {

            if (root == null) {
                return;
            }

            if (root.left != null) kthLargest(root.left, k);
            list.add(root.val);
            if (root.right != null) kthLargest(root.right, k);
        }*/

        // 倒中序
        public int kthLargest(TreeNode root, int k) {
            this.k = k;
            dfs(root);
            return res;
        }

        int res = 0;
        int k = 0;
        public void dfs(TreeNode root) {
            if(root == null) return;

            dfs(root.right);
            k--;
            if(k == 0) {
                res = root.val;
                return;
            }
            dfs(root.left);
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
